You are here: irt.org | FOLDOC | satisfiability problem
A problem used as an example in complexity theory. It can be stated thus:
Given a Boolean expression E, decide if there is some assignment to the variables in E such that E is true.A Boolean expression is composed of Boolean variables, (logical) negation (NOT), (logical) conjunction (AND) and parentheses for grouping. The satisfiability problem was the first problem to be proved to be NP-complete (by Cook).
["Introduction to Automata Theory, Languages, and Computation" by Hopcroft and Ullman, pub. Addison-Wesley].
(1994-11-11)
Nearby terms: SATAN « Sather « Sather-K « satisfiability problem » saturation » Saturday-night special » sausage code
FOLDOC, Topics, A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, ?, ALL